Synchronous (i.e., clocked or pulsed) circuits must operate within timing constraints. Synchronous logic circuits typically include a clock distribution network for providing a clock signal to various sub-circuits. A typical clock network includes one or more clock sources that are coupled to a number of clock “sinks.” A clock sink is any circuit or set of circuits accepting a clock input. In their simplest form, clock sinks are flip-flops and latches. Examples of more sophisticated sinks, involving several flip-flops or latches in the same time domain, include registers, counters, and state machines.
FIG. 1 illustrates clock distribution throughout parts of a synchronous logic circuit 100. The circuit 100 may be a VLSI (very large scale integration) integrated circuit, such as a microprocessor. The circuit 100 comprises a clock 110 and several clock sinks 120 connected to the clock 110 by clock lines (also called traces) 130. The circuit 100 also comprises logic circuits (not shown) interconnecting the sinks 120. The physical path lengths along the clock lines 130 to each sink 120 are generally different. Because of the non-uniform lengths of clock lines and other factors such as trace resistance, trace capacitance and load capacitance, clock pulses generally arrive at each sink 120 at different times. In other words, the clock signals are generally out of phase when they arrive at the sinks 120. A measure of this phase mismatch or non-uniformity in clock arrival time is “clock skew.” The skew between a clock signal at two points is the time delay or phase difference between the clock signals at those two points. In the circuit 100 having several clock sinks 120, maximum clock skew between any two sinks 120 is usually specified as some percentage (e.g., 10%) of the clock period.
Excessive clock skew is undesirable. If clock skew is too great, then the sinks 120 may fail to operate together properly. If a clock signal arrives at a sink 120 too early or too late relative to other events, then the circuit 100 may experience race conditions. Another negative consequence is that clock skew can be a limiting factor in how fast the clock 110 can operate. Misoperation and clock speed limitations result from violations of a setup or hold time of a sink 120.
FIGS. 2A and 2B illustrates setup and hold times for the case where the sink is a latch. FIG. 2A shows a dynamic latch 200 accepting an input D and a clock signal CLK. The dynamic latch 200 produces an output Q, which follows the input D, after a small delay, when the clock signal CLK is high and remains in the same state when the clock signal CLK is low. FIG. 2B shows waveforms of the clock signal CLK, the input D and the output Q. As shown in FIG. 2B, the input D pulses high briefly. In order for the output Q to follow the input D, the input pulse must be high for a setup time TS before the clock signal CLK falls low and stay high for a hold time TH after the clock signal CLK falls low. The setup time TS or the hold time TH may be violated if the clock signal CLK drifts, as can happen when there is excessive clock skew.
In the prior art, there are several approaches for minimizing clock skew. One approach is “retiming,” typified by U.S. Pat. No. 5,849,610. Retiming is physical placement of sinks and re-routing of clock lines to equalize path length. However, perfect distance equalization is seldom possible. Other design considerations often mandate sink and trace placement. Furthermore, physical distance is only one factor affecting propagation delay.
Another approach is the method of U.S. Pat. No. 6,075,832, which discloses variable delay elements on clock lines. The delay amounts are controlled by feedback control using a delay locked loop that dynamically equalizes delay during circuit operation. A disadvantage of this method is that it is complex, requiring extra space and power in the circuit.
Yet another approach is “clock scheduling,” such as disclosed in its most elementary form in U.S. Pat. No. 5,758,130. According to that patent, a delay is introduced along a shorter clock trace so as to synchronize its arrival with that of a longer clock trace. More generally, clock scheduling involves delaying clock signals before the clock inputs to various sinks, so that the clock signals arrive at their destination sinks at the same time (zero skew scheduling) or in some other desired relationship with each other (non-zero clock skew scheduling). Ivan S. Kourtney and Eby G. Friedman, “Timing Optimization through Clock Skew Scheduling,” Kluwer Academic Publishers, 2000 (ISBN 0-7923-7796-6), which is hereby incorporated by reference, discusses non-zero clock scheduling problem in great detail and discloses solutions based on linear programming and quadratic programming. Unfortunately, both techniques, which are entirely deterministic, do not always converge to a solution to this problem.